package org.example.search.binary;

/**
 * @author liyishan
 * @date 2024/4/7 13:48
 * @apiNote
 */

public class SearchTest {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,5,7,8,9,10};
        int res = test00035SearchInsert(nums,6);
        System.out.println(res);
    }
    /**
     * 基本用法
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static int[] test00167TwoSumPlus(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int mid = low + ((high - low) >> 1);
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }

    public boolean test00367IsPerfectSquare(int num) {
        int left = 0, right = num;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            long square = (long) mid * mid;
            if (square < num) {
                left = mid + 1;
            } else if (square > num) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    //============================================


    //test00035SearchInsert  尽量找大一点的数   就要合并目标值 小于等于num[mid] 的情况
    //test00069MySqrt        尽量找小一点的数   就要合并目标值 大于等于num[mid] 的情况

    /**
     * 找大于等于目标值的最小值
     * @param nums
     * @param target
     * @return 找第一个大于等于目标值的下标
     * right 是一直满足的但需要一个更满足的    left是一直不满足，直到结束前返回最后一个不满足的然后加一
     */
    public static int test00035SearchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        //找到left 和right 相交前
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            //因为要找第一个所以如果大于等于就往前找
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        //最后一次的 left = mid + 1   是找到了一个num[mid] 不满足 大于等于目标值， 所以取的是 mid + 1
        return left;
    }

    /**
     * 小于等于目标值的最大值
     * @param x
     * @return
     */
    public static int test00069MySqrt(int x) {
        int l = 0,r = x;
        while(l <= r){
            int mid = l+((r-l)>>1);
            long temp = (long) mid * mid;
            if(temp <= x){
                l = mid + 1;
            }else{
                r = mid -1;
            }
        }
        return r;
    }

    /**
     * 找小于等于目标值的最大值 因为数据一定在 1-x范围内  所以可以用 ans把满足条件的数据接住
     * @param x
     * @return 找小于等于目标值的最大值  （这里要的是ans  所以不需要考虑是否可以判断 mid ）
     */
    public static int test00069MySqrt01(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }


    /**
     * @param letters
     * @param target
     * @return 查找大于目标值的最小值（这里要的是left，所以 right不需要考虑是否可以判断 mid 本身）
     */
    public char nextGreatestLetter1(char[] letters, char target) {
        int length = letters.length;
        if (target >= letters[length - 1]) {
            return letters[0];
        }
        int low = 0, high = length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (letters[mid] > target) {
                high = mid-1;
            } else {
                low = mid + 1;
            }
        }
        return letters[low];
    }

    /**
     * 查找旋转排序数组中的最小值  4 5 6 1 2 3
     *
     * @param stock
     * @return
     */
    public int lcr128StockManagement(int[] stock) {
        int left = 0, right = stock.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (stock[mid] < stock[right]) {
                right = mid;
            } else if (stock[mid] > stock[right]) {
                left = mid + 1;
            } else {
                right--;
            }
        }
        return stock[left];
    }


    /**
     *
     * @param n
     * @return 查询前缀和小于等于目标值的最大值 （这里要的是left，所以需要考虑是否可以判断 mid 本身）
     */
    public static int test00441ArrangeCoins(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if ((long) mid * (mid + 1) <= (long) 2 * n) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

//=================================================

    public static int countTarget(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target) {
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }

    public static int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public int takeAttendance(int[] records) {
        int i = 0, j = records.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (records[m] == m) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }

    //=============================================================

    public int maximumCount1(int[] nums) {
        int pos1 = lowerBound(nums, 0);
        int pos2 = lowerBound(nums, 1);
        return Math.max(pos1, nums.length - pos2);
    }


    public static int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

}
